/*给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
* 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
*
* 输入：[1,1,1,3,3,2,2,2]
* 输出：[1,2]
* */

package Leetcode;

import java.util.*;

public class leetcode229 {

    public static void main(String[] args) {

        leetcode229 obj = new leetcode229();
        int[] nums = {1,1,1,3,3,2,2,2};
        System.out.println(obj.majorityElement(nums).toString());
    }

    public List<Integer> majorityElement(int[] nums){

        List<Integer> res = new ArrayList<>();
        int count1 = 0, count2 = 0, len = nums.length;
        int num1 = nums[0], num2 = nums[0];
        for (int i = 0;i < len;i++){
            if (num1 == nums[i]){
                count1++;
            }else if(num2 == nums[i]){
                count2++;
            }else if(count1 == 0){
                num1 = nums[i];
                count1++;
            }else if (count2 == 0){
                num2 = nums[i];
                count2++;
            }else {
                count1--;
                count2--;
            }
        }

        int res1 = 0, res2 = 0;
        for (int num : nums){
            if (num == num1){
                res1++;
            }else if(num == num2){
                res2++;
            }
        }
        if (res1 > len / 3){
            res.add(num1);
        }
        if (res2 > len / 3){
            res.add(num2);
        }
        return res;
    }
}
